package tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author Liangyaoyun
 */
public class TreeNode {
    private static class Node {
        Object data;
        List<Node> children = new ArrayList<>();

        public Node(Object data) {
            this.data = data;
        }
    }

    /*
     * 对于一般多叉树的先序深度优先遍历
     * 根的出现早于孩子节点
     * */
    //先序遍历
    public void dfsRootFirst(Node root) {
        System.out.print(root.data+" ");
        for (int i = 0; i < root.children.size(); i++) {
            /*
             * 此时得到的不仅仅是当前正在被遍历的root节点的一个下标为i的孩子
             * 也是root节点的一颗子树的树根
             * 如何对待整棵树，就如何对待任意子树
             * */
            dfsRootFirst(root.children.get(i));
        }
    }

    //后序遍历
    public static void dfsRootLast(Node root) {
        for (int i = 0; i < root.children.size(); i++) {
            /*
             * 此时得到的不仅仅是当前正在被遍历的root节点的一个下标为i的孩子
             * 也是root节点的一颗子树的树根
             * 如何对待整棵树，就如何对待任意子树
             * */
            dfsRootLast(root.children.get(i));
        }
        System.out.print(root.data+" ");
    }

    public void bfs(Node root) {
        //1.创建一个辅助队列
        Queue<Node> queue = new LinkedList<>();
        //2.初始状态下，将整棵树的树根加入队列
        queue.offer(root);

        while (!queue.isEmpty()){
            //3.执行广度优先遍历的流程
            Node tmp = queue.poll();

            System.out.println(tmp.data);

            for (int i = 0; i < tmp.children.size(); i++) {
                queue.offer(tmp.children.get(i));
            }
        }


    }

    public static void main (String[]args){
        Node A = new Node("A");
        Node B = new Node("B");
        Node C = new Node("C");
        Node D = new Node("D");
        Node E = new Node("E");
        Node F = new Node("F");
        Node G = new Node("G");
        Node H = new Node("H");
        Node I = new Node("I");
        Node J = new Node("J");
        Node K = new Node("K");
        Node L = new Node("L");

        A.children.add(B);
        A.children.add(C);

        B.children.add(D);

        C.children.add(E);
        C.children.add(F);
        C.children.add(G);


        D.children.add(H);
        D.children.add(I);
        D.children.add(J);
        D.children.add(K);
        D.children.add(L);

        TreeNode t = new TreeNode();

        // t.dfsRootFirst(A);
        //t.bfs(A);
        dfsRootLast(A);
    }
}
